/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
  class Solution {
  public:
      RandomListNode *copyRandomList(RandomListNode *head)
      {
          // Note: The Solution object is instantiated only once and is reused by each test case.
          if(head == NULL)return NULL;
          RandomListNode *result = NULL;
          RandomListNode *pold = head, *pnew = result, *poldNext = NULL;
          do
          {
             poldNext = pold->next;
             pnew = new RandomListNode(pold->label);
             pold->next = pnew;
             pnew->next = poldNext;
 
             if(result == NULL)
                 result = pnew;
             pold = poldNext;
         }while(pold);
         //设置new list的random指针
         pold = head;
         while(pold)
         {
             if(pold->random)
                 pold->next->random = pold->random->next;
             pold = pold->next->next;
         }
         //恢复old list 和new list
         pold = head;
         pnew = result;
         while(pnew->next)
         {
             pold->next = pnew->next;
             pold = pold->next;
             pnew->next = pold->next;
             pnew = pnew->next;
         }
         pold->next = NULL;
         pnew->next = NULL;
         return result;
      }
 };